In a typical video coding system, the video input is in the form of consecutive image frames, with each frame comprising a number of pixels. Although each frame could be individually coded and transmitted to a receiver where it can be decoded and displayed, a key point for improving video coding efficiency is to achieve bit rate saving while maintaining a given image quality. To achieve this, there are several different techniques within current video coding technologies that try to reduce the number of bits that need to be coded and transmitted. These are:                (i) motion estimation (ME) and motion compensation (MC) mode selection;        (ii) field/frame based Discrete Cosine Transformation (DCT) mode selection;        (iii) quantisation driven by rate control algorithm; and        (iv) entropy coding.        
Motion estimation and motion compensation seek to remove the temporal-domain redundancy present in natural video sources. Therefore motion estimation is important to a video coding system. However motion estimation is also the most computational complex element in a video coding system, especially for real-time full-motion video communication which requires a real-time implementation of a video encoder with a large motion search window. The search window of motion displacements can be as large as ±128 pixels in the MPEG-2 Main Profile and Main Level standard, as described in ISO/IEC Standard 13818-2, Generic coding of moving pictures and associated audio information: Video 1995, and can be much larger in high-resolution and high-quality entertainment video applications.
It will therefore be appreciated that a commercial implementation of real-time block matching motion estimation (ME) involves considering memory bandwidth (the required amount of data fetching from frame buffer to the ME processor), a search pattern to be used (the motion searching complexity within a given search window or fast search algorithm), a matching metric to be used (the basic matching complexity for each matching operation or block matching metrics), and the suitability of the process for real-time hardware implementations (the ability of the process to be efficiently pipelined).
Motion estimation involves matching of a block in a current frame with a block in a reference or previous frame. A full-search block matching technique using original pixel values examines all possible motion displacements, known as motion vectors (MV), within the search window to find the best match in terms of a predetermined distortion criterion. Due to the heavy computation and extensive data fetching required between the frame buffer and the processor performing the motion estimation, a full-search motion estimation using pixel intensities is only used for motion search in relatively small search ranges. Thus, many fast searching schemes have been developed to reduce computation and data fetching. Some of these are described by J. Feng, K. T Lo and H. Mehrpour, in “MPEG Compatible Adaptive Block Matching Algorithm for Motion Estimation”, published in Australian Telecommunication Networks and Applications Conference, December 1994; by J. N Kim and T. S Choi, in “A Fast Motion Estimation for Software Based Real-Time Video Coding”, published in IEEE Transactions on Consumer Electronics, Vol 45, No 2, pp 417-425, May 1999; by B. Liu and A. Zaccarin, in “A Fast Algorithm for the Estimation of Block Motion Vectors”, published in IEEE Transactions of Circuits and Systems for Video Technology, Vol 3, pp 730-741, April 1993; and by J. Chalidabhongse and C. C. Jay Kuo, in “Fast Motion Estimation Using Multiresolution-Spatio-Temporal Correlations”, published in IEEE Transactions of Circuits and Systems for Video Technology, Vol 7, No. 3, pp 477-488, June 1997.
To complicate matters, in interlaced video, alternate lines of each frame are generated at different times. For example the odd lines, forming one field, and the even lines, forming another field, are generated separately, even though the odd and even lines are interlaced with each other. Because of the time difference between generation of the two fields, looking for positional changes in a block between one frame and another causes complications. To deal with interlaced video data format, both MPEG-2 and MPEG-4 standards have functionalities to code full CCIR Rec. 601 resolution (i.e. 720×480 @60 HZ interlaced field rate). As defined in the MPEG 2 standard, video format follows the Rec. 601 interlaced form. Therefore, further consideration must be given to deal with interlaced format video. A simple approach would be to merge each pair of fields to form a frame. However, as the two fields are generated at different times ({fraction (1/50)}th of a second apart for Rec. 601 @25 Hz), moving objects are in different places in each field and so do not merge well. Another approach would be to code the even and odd fields separately.
The decision to code in frame mode or in field mode can be made at the macro block level. A macro block, which has dimensions of 16×16 pixels, is composed of even field lines and odd field lines arranged in an interlaced format. To find the best mode of coding, results of motion estimation in the frame mode is compared with results of motion estimation in the field mode. The decision to code either in frame or field mode depends on both error residue and motion vectors (MV) produced by motion estimation. Unfortunately, such an approach can be computationally expensive.
In U.S. Pat. No. 5,737,023 there is described a system and method for performing motion estimation on interlaced frames by refinement. However, the system and method does not provide reduced search areas for field motion estimation after determining a possible suitable block match associated with a potential motion vector.
In this specification, including the claims, the terms ‘comprises’, ‘comprising’ or similar terms are intended to mean a non-exclusive inclusion, such that a method or apparatus that comprises a list of elements does not include those elements solely, but may well include other elements not listed.